home *** CD-ROM | disk | FTP | other *** search
/ MacFormat España 13 / MacFormat n. 13 (Spain) / Macformat 13.bin / Shareware Internet / Educación / xComputer 1.2 / Examples / Example 4 - 3N+1 < prev    next >
Encoding:
Text File  |  1995-12-29  |  3.8 KB  |  88 lines
  1. ; Example 4: 3N+1
  2.  
  3. ; This file doesn't illustrate anything in particular about
  4. ; the xComputer.  It's just that I really like the 3N+1
  5. ; problem.
  6.  
  7. ; Starting from any positive integer N, the "3N+1 sequence"
  8. ; for N is computed as follows:  If N is 1, then stop; the
  9. ; sequence is complete.  Otherwise, if N is even then divide
  10. ; N by 2.  Otherwise (if N is odd), multiply N by three and
  11. ; add 1.  The question is whether this sequence terminates
  12. ; for ALL starting values N.  The answer is not known at 
  13. ; this time.
  14.  
  15. ; This program computes 3N+1 sequences for all values of
  16. ; N -- as long as you let it keep computing -- starting
  17. ; with 1.  (The program itself is stored starting at
  18. ; location 900, so you can't really let the starting value
  19. ; become bigger than 900.)  It counts the number of terms in
  20. ; each sequence and stores the answer for starting value N in 
  21. ; memory location N.  However, if in the course of the
  22. ; computation N becomes greater than the maximum allowed
  23. ; value (65535), I stop computing and store a -1 in the
  24. ; corresponding memory location to indicate an incomplete
  25. ; calculation.
  26.  
  27. ; Run this with "Fastest" run speed and "Graphics" memory
  28. ; display and watch memory fill up!
  29.  
  30.  
  31. @PC 900  ; Make sure the PC is set to 900, the starting
  32.          ;   location of the program.
  33.  
  34. 1024# 0  ; Clear out memory by storing 1024 zeros.
  35.  
  36. @900     ; Start loading at locatin 900
  37.  
  38.        lod-c 1    ; Let num = 1.  "Num" is the starting
  39.        sto num    ;   value for the current sequence
  40.  
  41. loop1: sto N      ; "Loop1" computes one sequence; get the starting
  42.                   ;    value from the AC, which now contains "num".
  43.        lod-c 1    ; "Ct" keeps track of the number of terms
  44.        sto ct     ;     in the sequence; start counting at 1.
  45.  
  46. loop2: lod N      ; "Loop2" computes one term in the sequence.
  47.        dec        ; Test if N=1 by subtracting 1 from it and
  48.        jmz next   ;    testing if the answer is 0.  If so, this
  49.                   ;    sequence is complete; jump to "next" to
  50.                   ;    get ready for the next sequence.
  51.        and-c 1    ; Compute bitwise logical AND of 1 with N-1.
  52.        jmz odd    ; If the answer is 0, N is odd; jump to
  53.                   ;    location "odd" to handle that case.
  54.        lod N      ; Otherwise, N is even; divide N by 2 by
  55.        shr        ;    shifting it right, and putting the
  56.        sto N      ;    result back into N.  Then jump to
  57.        jmp count  ;    "count" where this term in the sequence
  58.                   ;    is counted.
  59. odd:   lod N      ; If N is odd, multiply it by 3 by adding it
  60.        add N      ;    it to itself twice.  Then add 1.
  61.        jmf error  ;    If any of these additions produces a
  62.        add N      ;    result greater than 65535, the FLAG
  63.        jmf error  ;    register is set.  This indicates an
  64.        add-c 1    ;    error: "Number too large for this
  65.        jmf error  ;    computer".  Jump to "error" if the
  66.        sto N      ;    FLAG is set.
  67.  
  68. count: lod ct     ; Count this term in the sequence by
  69.        inc        ;    incrementing the value of ct.
  70.        sto ct
  71.        jmp loop2  ; Return to start of "loop2" to do the
  72.                   ;    next term in the sequence.
  73.  
  74. next:  lod ct     ; The 3N+1 sequence for the current starting
  75.        sto-i num  ;    value, num, is complete.  Store the
  76.        lod num    ;    number of terms in the sequence in the
  77.        inc        ;    location given by the value of num,
  78.        sto num    ;    then add 1 to num and jump back to
  79.        jmp loop1  ;    "loop1" to compute the next sequence.
  80.  
  81. error: lod-c 0    ; A term in the current sequence has
  82.        dec        ; exceeded 65535.  Store -1 (computed
  83.        sto ct     ; as zero minus one) in ct and jump to
  84.        jmp next   ; "next" to get ready for the next sequence.
  85.  
  86. num:   data   ; starting value of sequence
  87. ct:    data   ; number of terms in the sequence
  88. N:     data   ; current value of N in sequence